// ++++++++++++++++++++++++++++++++++++++++
// 《零基础Go语言算法实战》源码
// ++++++++++++++++++++++++++++++++++++++++
// Author:廖显东（ShirDon）
// Blog:https://www.shirdon.com/
// Gitee:https://gitee.com/shirdonl/goAlgorithms.git
// Buy link :https://item.jd.com/14101229.html
// ++++++++++++++++++++++++++++++++++++++++

package main

import "fmt"

// boyerMooreSearch 函数执行 Boyer-Moore 算法以在给定文本中搜索模式并返回找到模式的索引
// 如果未找到模式，则返回 -1
func boyerMooreSearch(text string, pattern string) int {
	// 文本长度
	n := len(text)
	// 模式的长度
	m := len(pattern)

	// 如果模式为空，则返回 0
	if m == 0 {
		return 0
	}

	// 如果模式比文本长，返回 -1
	if n < m {
		return -1
	}

	// 初始化最后一个数组以存储模式中每个字符的最后一个索引
	last := make([]int, 256)
	for i := 0; i < 256; i++ {
		last[i] = -1
	}

	// 存储模式中每个字符的最后一次出现
	for i := 0; i < m; i++ {
		last[pattern[i]] = i
	}

	// 初始化指向模式末尾的 i 和 j 指针
	i := m - 1
	j := m - 1

	// 在文本中执行模式搜索
	for i < n {
		// 如果字符匹配，将 i 和 j 指针向左移动
		if text[i] == pattern[j] {
			// 如果找到整个模式，则返回模式在文本中的起始索引
			if j == 0 {
				return i
			}
			i--
			j--
		} else { // 如果字符不匹配，则在最后一个数组的基础上将 i 指针移动 k 步，
			// 并将 j 指针重置为 m-1
			k := last[text[i]]
			i += m - min(j, 1+k)
			j = m - 1
		}
	}

	// 没有找到模式，返回-1
	return -1
}

// min 函数返回两个整数中的最小值
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func main() {
	// 要在其中搜索模式的文本
	text := "I love Go algorithms, this is an example"
	// 在文本中搜索的模式
	pattern := "love"
	// 使用 Boyer-Moore 算法在文本中找到模式的起始索引
	index := boyerMooreSearch(text, pattern)

	// 如果没有找到模式，打印一条消息
	if index == -1 {
		fmt.Println("在文本中找不到模式")
	} else { // 如果找到模式，则在文本中打印模式的起始索引
		fmt.Printf("在文本中的索引 %d 处找到模式\n", index)
	}
}

//$ go run boyerMooreSearch.go
//在文本中的索引 2 处找到模式
